Semana Uno

En esta semana se introdujeron conceptos de programación y recursividad.

Luego se presentó una solución para fibonacci usando recursividad y se presentó la técnica de programación dinámica.

Se implementó fibonacci con dos enfoques programación dinámica: top - down y bottom up.



In [1]:

    
def fib(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  return fib(n - 1) + fib(n - 2)



In [2]:

    
[fib(i) for i in range(10)]









    Out[2]:





[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]



In [3]:

    
def fibpd(n):
  fibn = []
  for i in range(n):
    if i == 0:
      fibn.append(0)
    elif i == 1:
      fibn.append(1)
    else: 
      fibn.append(fibn[i - 1] + fibn[i - 2])
  return fibn[n-1]



In [4]:

    
fibpd(10)









    Out[4]:





34



In [5]:

    
G = [60,100,120]
V = [10, 20, 30]
M = 50

def mochila(V,G,m,g,n):
  if n == 0 or m == 0:
    return 0
  else:
    if V[n-1] > m:
      return mochila(V,G,m,g,n-1)
    else:
      return max(mochila(V,G,m-V[n-1],g,n-1) + G[n-1], mochila(V,G,m,g,n-1))



In [6]:

    
mochila(V,G,M,0,3)









    Out[6]:





220



In [7]:

    
def mochilaPDBU(V,G,m,g,n):
  matriz = [[0 for x in range(n+1)] for y in range(m+1)] 
  for i in range(m+1):
    for j in range(n+1):
      if i == 0 or j == 0:
        matriz[i][j] = 0
      else:
        if V[j-1] > i:
          matriz[i][j] = matriz[i][j-1]
        else:
          matriz[i][j] = max(matriz[i-V[j-1]][j-1] + G[j-1], matriz[i][j-1])
  return matriz[m][n]



In [8]:

    
mochilaPDBU(V,G,M,0,3)









    Out[8]:





220



In [54]:

    
def sumaN(N, C, i, j):
  if j == 0:
    if i == 0:
      return 1
    else:
      return 0
  else:
    return max(sumaN(N,C, i, j-1), sumaN(N,C, i - C[j-1], j - 1))



In [55]:

    
sumaN(10, [4,3,2,1], 10, 4)









    Out[55]:





1



In [56]:

    
sumaN(10, [4,3,2], 10, 3)









    Out[56]:





0



In [479]:

    
def sumaNBU(N, C):
  cuantos = len(C)
  s = 0
  M = [[ 0 for x in range(N+1)] for y in range(cuantos+1)]

  for i in range(cuantos+1):
    M[i][0] = 1

  for j in range(1,N+1):
    for i in range(1,cuantos+1):
      if C[i-1] > j:
        M[i][j] = M[i-1][j]
      else:
        M[i][j] = max(M[i-1][j-C[i-1]],M[i-1][j])

  for j in range(N+1):
    s = ""
    for i in range(cuantos+1):
      s += " %d " % M[i][j]
    print "%s\n"%s
        
  return M[cuantos][N]



In [488]:

    
#sumaNBU(7,[4,3,2,1])
sumaNBU(3, [2,5,1,9])









    



 1  1  1  1  1 

 0  0  0  1  1 

 0  1  1  1  1 

 0  0  0  1  1 







    Out[488]:





1



In [492]:

    
sumaNBU(13, [8,3,4,11,3])









    



 1  1  1  1  1  1 

 0  0  0  0  0  0 

 0  0  0  0  0  0 

 0  0  1  1  1  1 

 0  0  0  1  1  1 

 0  0  0  0  0  0 

 0  0  0  0  0  1 

 0  0  0  1  1  1 

 0  1  1  1  1  1 

 0  0  0  0  0  0 

 0  0  0  0  0  1 

 0  0  1  1  1  1 

 0  0  0  1  1  1 

 0  0  0  0  0  0 







    Out[492]:





0

Para x de 0 a n Para y de 0 a n Si x=0 o y=0 L[x,y] = 0 Si no Si v[x] = w[y] L[x,y] = max(L[x-1,y-1], L[x-1,y], L[x,y-1]) Si no L[x,y] = max(L[x-1,y], L[x,y-1])



In [545]:

    
def longitudAlineamiento(v,w):
  m = len(v)
  n = len(w)
  
  M = [[ 0 for x in range(n+1)] for y in range(m+1)]

  for j in range(n+1):
    for i in range(m+1):
      if j == 0 or i == 0:
        M[i][j] = 0
      else:
        if v[i-1] == w[j-1]:
          M[i][j] = max(M[i-1][j-1]+1, M[i][j-1], M[i-1][j])
        else:
          M[i][j] = max(M[i][j-1], M[i-1][j])

  for j in range(n+1):
    s = ""
    for i in range(m+1):
      s += " %d " % M[i][j]
    print "%s\n"%s
  
  return M[m][n]



In [547]:

    
longitudAlineamiento("cgacgacta","cgat") # deberíamos obtener un 4









    



 0  0  0  0  0  0  0  0  0  0 

 0  1  1  1  1  1  1  1  1  1 

 0  1  2  2  2  2  2  2  2  2 

 0  1  2  3  3  3  3  3  3  3 

 0  1  2  3  3  3  3  3  4  4 







    Out[547]:





4



In [14]:

    
def alineamiento(v,w):
  m = len(v)
  n = len(w)
  
  M = [[ 0 for x in range(n+1)] for y in range(m+1)]
  N = [[ 0 for x in range(n+1)] for y in range(m+1)]

  for j in range(n+1):
    for i in range(m+1):
      if j == 0 or i == 0:
        M[i][j] = 0
        N[i][j] = (0,0)
      else:
        if v[i-1] == w[j-1]:
          M[i][j] = max(M[i-1][j-1]+1, M[i][j-1], M[i-1][j])
          if (M[i][j] == M[i-1][j-1]+1):
            N[i][j] = (i-1,j-1)
          elif M[i][j] == M[i][j-1]:
            N[i][j] = (i,j-1)
          else:
            N[i][j] = (i-1,j)
        else:
          M[i][j] = max(M[i][j-1], M[i-1][j])
          if M[i][j] == M[i][j-1]:
            N[i][j] = (i,j-1)
          else:
            N[i][j] = (i-1,j)
  
  alineadas = [[],[]]
  ultI = m-1
  ultJ = n-1
  seguridad = 0
  while ((ultI >= 0 or ultJ >= 0) and seguridad < 10):
    t = N[i][j]

    i = t[0]
    j = t[1]

    while ultI >= i:
#      print "v:%s"%v[ultI]
      alineadas[0].insert(0, v[ultI])
      alineadas[1].insert(0, '-')
      ultI = ultI - 1
    
    while ultJ >= j:
#      print "w:%s"%w[ultJ]
      alineadas[0].insert(0, '-')
      alineadas[1].insert(0, w[ultJ])
      ultJ = ultJ - 1
    
    if (v[ultI] == w[ultJ]):
      alineadas[0].insert(0, v[ultI])
      alineadas[1].insert(0, w[ultJ])
      ultI = ultI - 1
      ultJ = ultJ - 1
    
    seguridad = seguridad + 1

  return alineadas



In [19]:

    
alineamiento( "cgtacgacta", "ta")









    Out[19]:





[['a', 'c', 'g', 't', 'a', 'c', 'g', 'a', 'c', 't', '-', 'a'],
 ['a', '-', '-', '-', '-', '-', '-', '-', '-', 't', 'a', '-']]



In [ ]: